//图的边的结构体(也可以用来表示树)
struct LinkList
{
    //节点编号
    int index;
    //所有连接节点的边 包括根节点
    LinkList* next;
    LinkList* pre;
};

LinkList* newLinkList(int value)
{
    LinkList* newItem=new LinkList;
    newItem->index=value;
    newItem->next=NULL;
    newItem->pre=NULL;
    return newItem;
}

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//添加单项边
void addSinglEv(LinkList** ev,int start,int end)
{
    LinkList* l=newLinkList(end);

    if(ev[start]==NULL)
    {
        ev[start]=l;
    }
    else{
        l->next=ev[start];
        ev[start]=l;
    }
}

void addLinkList(LinkList** ev,int index,LinkList* l)
{
    if(ev[index]==NULL)
    {
        ev[index]=l;
    }
    else{
        l->next=ev[index];
        ev[index]->pre=l;
        ev[index]=l;
    }
}

//添加双向边
void addEv(LinkList** ev,int start,int end){
    //添加双向边
    LinkList* l=newLinkList(end);
    addLinkList(ev,start,l);

    l=newLinkList(start);
    addLinkList(ev,end,l);
}